1. Technical Field
The invention relates generally to computers and data processing systems, and more particularly relates to numeric processing including subtractive division computations.
In even greater particularity, the invention relates to detecting overflow conditions in nonrestoring two's complement division.
2. Related Art
Microprocessor architectures include execution units that perform basic arithmetic operations such as addition, subtraction, multiplication, division, and shifting. These operations may use either signed or unsigned numbers--in the case of signed integers (where the most significant bit is the sign bit), the most common form of representation is two's complement. Sign-magnitude is also used, in particular for floating point computations following the IEEE 754 Floating Point standard.
For division, the common approach is to use a subtractive division algorithm that implements shift-and-subtract division, such as nonrestoring division, although some processor architectures (typically, floating point processors) implement division algorithms where multiplication is the iterative operator. Basically, conventional nonrestoring integer division involves iteratively subtracting an n bit divisor from an appropriately shifted 2n bit dividend to obtain an n bit quotient and an n bit remainder. By convention, any non-zero remainder should be of the same sign as the dividend and smaller in magnitdue than the divisor.
Overflow should be signaled if the values of the 2n bit dividend and the n bit divisor are such that the quotient won't fit in n bits. In particular, two types of overflow can occur: (a) absolute overflow where either the divisor is zero or the dividend is so large (in absolute value) as to guarantee overflow for any n bit divisor, and (b) relative overflow where a given dividend is too large relative to a given divisor.
Without limiting the scope of the invention, this background information is provided in the context of a specific problem to which the invention has application: for conventional nonrestoring division using two's complement integers, detecting and signaling overflow conditions as soon as possible.
Nonrestoring division using a subtractive division algorithm implements a variation of basic pencil-and-paper division--in successive iterative steps, after appropriate shifting, the divisor is iteratively subtracted from the dividend or partial remainder to obtain a quotient digit and a new partial remainder, finally obtaining a full quotient and a final remainder that is zero or at least smaller in magnitude than the divisor.
The basic process is (assuming positive dividend and divisor): (a) loading the 2n bit dividend into a double length register and the n bit divisor into a single length register aligned with the most significant n bits (or high order part) of the dividend, (b) in a first iterative step, subtracting the divisor from the high order part to obtain a first partial remainder no larger than 2n-1 bits, and (c) in successive iterative steps, left shifting the partial remainder and either (i) subtracting the divisor if the partial remainder is positive, or (ii) adding the divisor if the partial remainder is negative. The general principle is that each iteration should bring the allowable range of the partial remainder closer to zero, i.e., the iterative process is repeated until the partial remainder converges to a final remainder that is zero or at least smaller in magnitude than the divisor.
For negative quotients (either dividend or divisor negative), the general principle remains that each iteration should bring the alowed range of the partial remainder closer to zero. Thus, the first iterative step requires an addition (of two oppositely signed numbers), followed by successive iterative steps in which the divisor is added or subtracted from the partial remainder depending on the their signs.
Overflow detection depends on the type of nonrestoring division being implemented: (a) unsigned, (b) signed magnitude, or (c) two's complement. Absolute overflow may be determined by inspection of the dividend and/or divisor before commencing the iterative subtractive operations. Determination of instances of relative overflow are usually made after the first and/or after the last iterative subtraction, depending on the type of nonrestoring division implemented.
For unsigned integer divide, the 2n bit dividend and the n bit divisor are both magnitude fields:
0.ltoreq.Dividend.ltoreq.2.sup.2n -1 PA1 0.ltoreq.Divisor.ltoreq.2.sup.n -1 PA1 [0] if Dividend-2.sup.n .times.Divisor.ltoreq.0 PA1 [1] if Dividend-2.sup.n .times.Divisor&lt;0
The overflow test is based on the sign bit of the first partial remainder PR1(s), which is equal to:
(multiplying by 2.sup.n corresponds to shifting the Divisor left by n bits).
If PR1(s)=[0] (non-negative), then either (i) the divisor is zero, or (ii) the quotient will be greater than or equal to 2.sup.n, which overflow--if PR1(s)=[1] (negative), the quotient must be strictly less than 2.sup.n, and overflow cannot occur. Thus testing the negative or non-negative status of the difference [Dividend-2.sup.n .times.Divisor] provides a simple early overflow test (i.e., a test that can be completed prior to computing the computing the second partial remainder).
In practice, the subtraction determining PR1(s) can be effected by adding the n bit two's complement of the divisor to the leading n bits of the dividend, with the complement of the carry out corresponding to the sign bit PR1(s) (this use of complement carry out prevails for all successive partial remainder sign computations as the associated iterative subtraction or addition steps are effectively additions of oppositely signed values). Note that if sign extension by one bit could be used (i.e., if the dividend and divisor registers were correspondingly extended by one bit each to provide a leading sign bit position), then the effective sum of the dividend and complemented divisor in the extended sign position would become [0+1+(carry out)] which is equivalent to using complement carry out as the sign bit PR1(s).
For sign magnitude type integer divide, the 2n bit dividend has a sign bit and [2(n-1)+1] magnitude bits, such that: EQU .vertline.Dividend.vertline..ltoreq.2.sup.2n-1 -1
while the divisor has a sign bit and (n-1) magnitude bits, such that: EQU .vertline.Divisor.vertline..ltoreq.2.sup.n-1 -1
Note that the dividend here has twice the number of magnitude bits of the divisor plus one extra leading magnitude bit.
Two implementations of the iterative subtractive operation can be used, both of which are able to signal overflow prior to computing the second partial remainder.
The first implementation uses an (n-1) bit adder, and requires two overflow tests, selected by testing the most significant magnitude bit (MSB) of the dividend (the extra magnitude bit): (a) for MSB=1, a range exception (indicative of absolute overflow) exists and overflow is signaled, and (b) for MSB=0, overflow is signaled if the resulting sign of the first partial remainder (complement carry out) is non-negative. For the latter case, the dividend and divisor signs are shifted out along with the dividend MSB, leaving an unsigned 2(n-1) bit dividend and unsigned (n-1) bit divisor, transforming the iterative subtractive operation into (n-1) bit unsigned divide (the dividend and divisor signs are used after the iterative subtractive steps to determine the signs of any non-zero quotient and remainder).
The second implementation uses an n bit adder, and requires only one overflow test. The sign of the dividend is shifted out to obtain an unsigned 2n-1 bit dividend, and the divisor sign is extracted and replaced by a zero to obtain an unsigned n bit divisor. The first partial remainder is formed by two's complement addition using the n-bit adder, and overflow is signaled if the resulting sign (the complement of the carry out) is non-negative.
Signaling overflow for two's complement nonrestoring integer division is more problematic. Because the range of allowed n bit quotients is asymmetric--(-2.sup.n) to +(2.sup.n -1) --anomalous overflow conditions can occur.
A common approach to resolving the distinction between whether a legitimate quotient of -2.sup.n is obtained or whether a negatively directed overflow corresponding to a quotient of .ltoreq.-(2.sup.n +1) has occurred is to perform a final overflow test, i.e., after the iterative subtractive step has obtained a final quotient and remainder. See, for example, "Introduction to Arithmetic For Digital Systems Designers", S. Waser and M. Flynn, (Pub. 1982 CBS College Publishing) ("Flynn").
The overflow technique in Flynn fails to detect an anomalous absolute overflow condition that can occur where the 2n bit dividend is so large that for any n bit divisor overflow must occur. The first related application describes an overflow detection technique that includes two overflow detection tests: (a) an early overflow detection for this anomalous overflow condition, i.e., determining if the first partial remainder is sufficiently large in magnitude that overflow must occur for any n-bit divisor, and (b) a second overflow detection test (such as taught in Flynn) to signal overflow after the iterative divide operation is complete and an adjusted signed quotient is obtained. In one embodiment, overflow is signaled if complement carry out from the n-bit subtraction that computes the first partial remainder is not the same as the most significant bit of the first partial remainder.
This overflow detection technique taught by the first related application requires a final overflow detection test that is not performed until after the iterative divide operations are complete, a delay involving on the order of n iterations for n bit division. The delay for final resolution of overflow can create an unnecessary bottleneck in systems that allow parallel instruction execution with out-of-order completion but require exceptions to be signaled in order (i.e., precise exceptions) such that a delay in determining whether a computation will cause an overflow exception will prevent other completed instructions from retiring.
Alternative overflow tests for nonrestoring two's complement division are disclosed in European Patent 351,829 (to Yamahata) and U.S. Pat. No. 5,317,531 (to Zaidi). Both of these references use the dividend and divisor signs for a final determination of quotient sign. The operable dividend and divisor values are complemented as needed to obtain positive magnitudes, and 2n by n bit unsigned division is performed--a final overflow test after determining a final quotient magnitude is performed to resolve the distinction between the legitimate quotient -2.sup.n and other quotient overflow values. These overflow tests similarly involve an order of n iteration delay in resolving overflow detection.
U.S. Pat. No. 5,097,435 (to Takahashi) discloses three implementations for multiple-step overflow detection for nonrestoring two's complement division: (a) testing for a zero result, and if the result is not zero signaling overflow based on an XNOR of the dividend sign and the carry out (see, FIG. 2a-2b), (b) determining whether the dividend and the divisor have the same sign, and the MSB of a quotient is equal to one (see, FIG. 5), and (c) determining during each iterative cycle for computing a next quotient bit whether for oppositely signed dividend and divisor the quotient bit and MSB-of-quotient bit are both one (FIG. 5). Each of these overflow tests are not sufficient to determine all cases of overflow prior to the computation of the second partial remainder.
Thus, currently available overflow detection techniques for two's complement nonrestoring integer division require that numerous iterative shift-and-subtract operations be completed before all cases of overflow can be detected (and/or before it can be detected that overflow will not occur). Completing these iterative operations typically requires on the order of 32 clocks for 64 bit dividends and 32 N bit divisors.